// 3Sum.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
//Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? 
//Find all unique triplets in the array which gives the sum of zero.
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int> > threeSum(vector<int> &num) 
{
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    vector<vector<int>> results;
	if(num.size() < 3) return results;
	sort(num.begin(), num.end());
	for(int i = 0; i< num.size() -1; i++)
	{
		int k = num.size() -1;
		int j = i+1;
		int nTarget = num[i];
		while(j<k)
		{
			vector<int> triplet;
			triplet.push_back(num[i]);
			triplet.push_back(num[j]);
			triplet.push_back(num[k]);
			
			int nSum = num[j]+num[k];
				
			if(nSum == abs(nTarget)) 
			{
				results.push_back(triplet);
				int tempJ = num[j];
				int tempK = num[k];
				while(j<k && num[j]== tempJ)
					j++;
				while(j<k && num[k]==tempK)
					k--;
			}
			else if(nSum <nTarget)
			{
				int tempJ = num[j];
				while(j<k && num[j]== tempJ)
					j++;
			}
			else
			{
				int tempK = num[k];
				while(j<k && num[k]==tempK)
					k--;
			}

		}
	}

	return results;
}

int _tmain(int argc, _TCHAR* argv[])
{
	vector<vector<int>> ret;
	int testData[5] = {-2,0,1,1,2};
	vector<int> testcase(testData, testData+5);

	ret = threeSum(testcase);
	return 0;
}

